#include "QuadTree.h"
#define SCR 256;
extern CObjects *ArrayObj[100];
#include "trace.h"

QuadNode::QuadNode()
{
	LT = LB = RT = RB = NULL;
	lvl = -1;
	sqr = new mySquare;
	sqr->x = -1;
	index = -1;
}

QuadNode::~QuadNode()
{
	delete LT;
	delete RB;
	delete RT;
	delete LB;
	delete sqr;
}

QuadTree::QuadTree(int h)
{
	Root = new QuadNode();
	Root->lvl = h;
	Root->sqr->x = 0;
	Root->sqr->y = 0;
	Root->sqr->length = 4096;
}

void QuadTree::AddPixel(QuadNode *node,int Index,int XX,int YY)
{
	if(node->lvl == 1)
	{
		node->index = Index;
		return;
	}
	if(node->LB == NULL)
		node->LB = new QuadNode();
	if(node->RB == NULL)
		node->RB = new QuadNode();
	if(node->LT == NULL)
		node->LT = new QuadNode();
	if(node->RT == NULL)
		node->RT = new QuadNode();

	int X = node->sqr->x;
	int Y = node->sqr->y;
	int Length = node->sqr->length / 2;
	int	midX = X + Length;
	int midY = Y + Length;

	if(XX >= midX)
	{
		if(YY >= midY)
		{
			if(node->RB->sqr->x == -1)
			{
				node->RB->sqr->x = midX;
				node->RB->sqr->y = midY;
				node->RB->lvl = node->lvl-1;
				node->RB->sqr->length = Length;
			}
			AddPixel(node->RB,Index,XX,YY);
		}
		else
		{
			if(node->RT->sqr->x == -1)
			{	
				node->RT->sqr->x = midX;
				node->RT->sqr->y = Y;
				node->RT->sqr->length = Length;
				node->RT->lvl = node->lvl-1;
			}
			AddPixel(node->RT,Index,XX,YY);
		}
	}
	else
	{
		if(YY >= midY)
		{
			if(node->LB->sqr->x == -1)
			{
				node->LB->sqr->x = X;
				node->LB->sqr->y = midY;
				node->LB->lvl = node->lvl-1;
				node->LB->sqr->length = Length;
			}
			AddPixel(node->LB,Index,XX,YY);
		}
		else
		{
			if(node->LT->sqr->x == -1)
			{
				node->LT->sqr->x = X;
				node->LT->sqr->y = Y;
				node->LT->lvl = node->lvl-1;
				node->LT->sqr->length = Length;
			}
			AddPixel(node->LT,Index,XX,YY);
		}
	}
}

void QuadTree::Add(CObjects *obj,int i)
{
	for(int j = 0; j < obj->width; j++)
		for(int k = 0; k < obj->height-1; k++)
			AddPixel(Root,i,obj->pos_x + j,obj->pos_y - k);
}

bool QuadTree::inRect(int x,int y,myRect *sqr)
{
	int X = sqr->x;
	int Y = sqr->y;
	int W = sqr->w;
	int H = sqr->h;
	if(x >= X && x <= X+W && y >= Y && y <= Y+H) 
		return true;
	return false;
}

bool QuadTree::CutX(myRect *sqr1,myRect *sqr2)
{
	int W = sqr1->w;
	int H = sqr1->h;
	if(inRect(sqr1->x,		sqr1->y,	sqr2)) return true;
	if(inRect(sqr1->x+W,	sqr1->y,	sqr2)) return true;
	if(inRect(sqr1->x,		sqr1->y+H,	sqr2)) return true;
	if(inRect(sqr1->x+W,	sqr1->y+H,	sqr2)) return true;
	return false;
}

bool QuadTree::existInResult(int k)
{
	for(int i = 0; i < lastRes; i++)
		if(k == res[i]) return true;
	return false;
}

void QuadTree::Search(QuadNode *node,myRect *Sqr)
{
	if(node == NULL) return;
	if(node->lvl == -1) return;

	myRect *rec = new myRect;
	rec->x = node->sqr->x;
	rec->y = node->sqr->y;
	rec->w = node->sqr->length;
	rec->h = node->sqr->length;

	if(!CutX(rec,Sqr) && !CutX(Sqr,rec))
	{
		delete rec;
		return;
	}
	if(node->lvl > 1)
	{
		Search(node->LT,Sqr);
		Search(node->RT,Sqr);
		Search(node->LB,Sqr);
		Search(node->RB,Sqr);
	}
	if(node->lvl == 1 && node->index != -1 && !existInResult(node->index))
		res[lastRes++] = node->index;
	delete rec;
}

void QuadTree::RenderScreen(int scr_x, int scr_y,LPDIRECT3DDEVICE9 d3ddv,int t)
{
	myRect * sqr = new myRect;
	if(scr_x < 80) sqr->x = 0;
	else
		sqr->x = scr_x-80;
	sqr->y = scr_y;
	sqr->w = 336;
	sqr->h = 256;
	lastRes = 0;
	Search(Root,sqr);
	for(int i = 0;i < lastRes;i++)
	{
		if(ArrayObj[res[i]]->life > 0 && ArrayObj[res[i]]->reality != 22)
			ArrayObj[res[i]]->RenderFrame(d3ddv,t);
	}
	delete sqr;
}

void QuadTree::Check(int pos_x,int pos_y,int W,int H)
{
	lastRes = 0;
	myRect *rec = new myRect;
	rec->x = pos_x;
	rec->y = pos_y;
	rec->h = H;
	rec->w = W;
	Search(Root,rec);
	delete rec;
}

void QuadTree::CheckCollision(CObjects *Obj)
{

}

void QuadTree::DelPixel(QuadNode * node,myRect *Sqr)
{
	if(node == NULL) return;
	if(node->lvl == -1) return;
	
	myRect *rec = new myRect;
	rec->x = node->sqr->x;
	rec->y = node->sqr->y;
	rec->w = node->sqr->length;
	rec->h = node->sqr->length;

	if(!CutX(rec,Sqr) && !CutX(Sqr,rec))
	{
		delete rec;
		return;
	}

	if(node->lvl > 1)
	{
		DelPixel(node->LT,Sqr);
		DelPixel(node->RT,Sqr);
		DelPixel(node->LB,Sqr);
		DelPixel(node->RB,Sqr);
	}
	if(node->lvl == 1 && node->index != -1)// && (node->index == type || type == -1))
	{
		result = node->index;
		if(type == -1) type = node->index;
		node->index = -1;
	}
	delete rec;
}

int QuadTree::Del(int pos_x,int pos_y, int width,int height)
{
	myRect* rec = new myRect;
	rec->x = pos_x+1;
	rec->y = pos_y-height;
	rec->h = height;
	rec->w = width-2;
	type = -1;
	DelPixel(Root,rec);
	delete rec;
	return result;
}

QuadTree::~QuadTree()
{

}